"""
# Definition for a Node.
"""
class Node:
    def __init__(self, val = 0, neighbors = []):
        self.val = val
        self.neighbors = neighbors


class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if node is None:
            return None
        adjList = [None for _ in range(101)]
        root = Node(node.val)
        adjList[node.val] = root
        todoList = [node]
        while len(todoList):
            todoNode = todoList.pop(0)
            nowNeighbors = []
            for neighbor in todoNode.neighbors:
                if adjList[neighbor.val] is None:
                    adjList[neighbor.val] = Node(neighbor.val)
                    todoList.append(neighbor)
                nowNeighbors.append(adjList[neighbor.val])
            adjList[todoNode.val].neighbors = nowNeighbors

        return root

if __name__ == '__main__':
    so = Solution()
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3)
    node4 = Node(4)

    node1.neighbors = [node2, node4]
    node2.neighbors = [node1, node3]
    node3.neighbors = [node2, node4]
    node4.neighbors = [node1, node3]

    re = so.cloneGraph(node1)
    print(re)
